#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define SEP '#'
template<class T>
struct BinaryTreeNode
{
	T data;
	BinaryTreeNode<T>* left;
	BinaryTreeNode<T>* right;
	BinaryTreeNode<T>* parent;

	BinaryTreeNode(const T& d)
		:data(d)
		, left(NULL)
		, right(NULL)
		, parent(NULL)
	{}
};

template<class T>
struct BinaryTree
{
private:
	typedef BinaryTreeNode<T> Node;
	typedef T NodeType;
public:
	BinaryTree()
		:_root(NULL)
	{}

	// 创建二叉树
	// 1.“根左子树右子树”的方式创建二叉树
	// ABD##E#H##CF##G##
	void crtTreeStr(const string& str)
	{
		int pos = 0;
		_crtTreeStr(_root, str, pos);
	}
	// 2. 读边创建二叉链表——层次遍历的运用
	void crtTreeEdge()
	{
		queue<Node*> q;
		char fa, ch;
		int lrflag;
		do
		{
			scanf("%c,%c,%d", &fa, &ch, &lrflag); getchar();
			if(ch == SEP) break;
			//cout << fa << ch << lrflag << endl;
			Node* p = new Node(ch);
			if (fa == SEP)
			{
				_root = p;
				q.push(_root);
			}
			else
			{
				q.push(p);
				Node* parent = q.front();
				while(parent->data != fa)
				{
					q.pop();
					parent = q.front();
				}
				if(lrflag == 0) parent->left = p;
				else parent->right = p;
			}
		} while (true);
	}
	// 3. 前序序列 + 中序序列 创建二叉树
	void crtTreePreIn(const vector<T>& pre, const vector<T>& in)
	{
		int prei = 0;
		_root = _crtTreePreMid(pre, in, prei, 0, in.size() - 1);
	}
	// 4. 中序序列 + 后序序列 创建二叉树
	void crtTreeInPost(const vector<T>& in, const vector<T>& post)
	{
		int posti = post.size() - 1;
		_root = _crtTreeInPost(in, post, posti, 0, in.size() - 1);
	}

	// 遍历二叉树
	// 1. 递归遍历
	void preOrder()
	{
		_preOrder(_root);
		cout << endl;
	}
	void inOrder()
	{
		_inOrder(_root);
		cout << endl;
	}
	void postOrder()
	{
		_postOrder(_root);
		cout << endl;
	}
	// 2. 非递归遍历
	// 2.1 任务分析法
	enum taskType
	{
		ACCESS =1, 
		VISIT
	};
	struct task
	{
		Node* node;
		taskType type;
		task(Node* n, taskType t)
			:node(n)
			, type(t)
		{}
	};
	void preOrderNorTask()
	{
		stack<task> s;
		s.push(task(_root, VISIT));
		while (!s.empty())
		{
			task t = s.top();
			s.pop();
			if (t.node == nullptr) continue;
			if (t.type == ACCESS)
			{
				cout << t.node->data << " ";
			}
			else
			{
				s.push(task(t.node->right, VISIT));
				s.push(task(t.node->left, VISIT));
				s.push(task(t.node, ACCESS));
			}
		}
		cout << endl;
	}
	void inOrderNorTask()
	{
		stack<task> s;
		s.push(task(_root, VISIT));
		while (!s.empty())
		{
			task t = s.top();
			s.pop();
			if (t.node == nullptr) continue;
			if (t.type == ACCESS)
			{
				cout << t.node->data << " ";
			}
			else
			{
				s.push(task(t.node->right, VISIT));
				s.push(task(t.node, ACCESS));
				s.push(task(t.node->left, VISIT));
			}
		}
		cout << endl;
	}
	void postOrderNorTask()
	{
		stack<task> s;
		s.push(task(_root, VISIT));
		while (!s.empty())
		{
			task t = s.top();
			s.pop();
			if (t.node == nullptr) continue;
			if (t.type == ACCESS)
			{
				cout << t.node->data << " ";
			}
			else
			{
				s.push(task(t.node, ACCESS));
				s.push(task(t.node->right, VISIT));
				s.push(task(t.node->left, VISIT));
			}
		}
		cout << endl;
	}
	// 2.2 标记法  
	// 原理：一颗二叉树的组成可以看成 左路结点 + 左路结点的右子树
	void preOrderNorMark()
	{
		stack<Node*> s;
		Node* cur = _root;
		while (cur || !s.empty()) 
		{
			while (cur)
			{
				cout << cur->data << " ";
				s.push(cur);
				cur = cur->left;
			}
			cur = s.top();
			s.pop();
			cur = cur->right;
		}
		cout << endl;
	}
	void inOrderNorMark()
	{
		stack<Node*> s;
		Node* cur = _root;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			cur = s.top();
			s.pop();
			cout << cur->data << " ";
			cur = cur->right;
		}
		cout << endl;
	}
	void postOrderNorMark()
	{
		stack<Node*> s;
		Node* cur = _root;
		Node* prev = nullptr; // 标记上一个访问的结点
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			cur = s.top();
			if (cur->right == nullptr || cur->right == prev) // 当前结点的右子树为空 或者 右子树已经访问过
			{
				cout << cur->data << " ";
				s.pop();
				prev = cur;
				cur = nullptr;
			}
			else
			{
				cur = cur->right;
			}
		}
		cout << endl;
	}
	// 3. 层序遍历
	void levelOrder()
	{
		queue<Node*> q;
		q.push(_root);
		while (!q.empty())
		{
			Node* front = q.front();
			q.pop();
			cout << front->data << " ";
			if (front->left)
				q.push(front->left);
			if (front->right)
				q.push(front->right);
		}
		cout << endl;
	}

	// 二叉树遍历的应用
	// 1. 求二叉树中结点的个数
	size_t size()
	{
		return _size(_root);
	}
	// 2. 求二叉树中叶子结点的个数
	size_t leafSize()
	{
		return _leafSize(_root);
	}
	// 3. 求二叉树的高度
	size_t height()
	{
		return _height(_root);
	}
	// 4. 求二叉树第K层结点的个数
	size_t kLevelSize(size_t k)
	{
		return _kLevelSize(_root, k);
	}
	// 5. 查找值为x的结点
	Node* find(NodeType x)
	{
		return _find(_root, x);
	}
	// 6. 求二叉树中两个结点的最近公共祖先结点
	Node* lowestCommonAncestor(Node* p, Node* q)
	{
		return _lowestCommonAncestor(_root, p, q);
	}
	// 7. 判断二叉树是否是完全二叉树
	bool isCompleteTree()
	{
		queue<Node*> q;
		q.push(_root);
		while (true)
		{
			Node* front = q.front();
			q.pop();
			if (front == nullptr)
				break;
			q.push(front->left);
			q.push(front->right);
		}
		while (!q.empty())
		{
			Node* front = q.front();
			q.pop();
			if (front != nullptr)
				return false;
		}
		return true;
	}
	// 8. 判断二叉树是否是满二叉树
	bool isFullTree()
	{
		return _isFullTree(_root);
	}
	// 9. 判断二叉树是否是平衡二叉树
	bool isBalanceTree()
	{
		return _isBalanceTree(_root);
	}

	// 以凹凸表的形式显示二叉树
	void display()
	{
		_display(_root, 0, 'D');
	}

	~BinaryTree()
	{
		destroy(_root);
		_root == nullptr;
	}

private:

	void destroy(Node* root)
	{
		if(root == nullptr) return;
		destroy(root->left);
		destroy(root->right);
		delete root;
	}

	bool _isBalanceTree(Node* root)
	{
		if (root == nullptr) return true;
		size_t leftHeight = _height(root->left);
		size_t rightHeight = _height(root->right);
		if (abs((int)(leftHeight - rightHeight)) > 1)
			return false;
		return _isBalanceTree(root->left) && _isBalanceTree(root->right);
	}

	bool _isFullTree(Node* root)
	{
		if (root == nullptr) return true;
		if (root->left == nullptr && root->right == nullptr) return true;
		if (root->left && root->right)
			return _isFullTree(root->left) && _isFullTree(root->right);
		return false;
	}

	Node* _lowestCommonAncestor(Node* root, Node* p, Node* q)
	{
		if (root == nullptr) return nullptr; // 空树
		if (root == p || root == q) return root; // p或q为根结点
		Node* left = _lowestCommonAncestor(root->left, p, q); // 在左子树中查找p或q
		Node* right = _lowestCommonAncestor(root->right, p, q); // 在右子树中查找p或q
		if (left && right) return root; // p和q分别在左右子树中
		return left ? left : right;     // p和q在同一子树中
	}

	Node* _find(Node* root,NodeType x)
	{
		if (root == nullptr) return nullptr;
		if (root->data == x) return root;
		Node* ret = _find(root->left, x);
		if (ret) return ret;
		return _find(root->right, x);
	}

	size_t _kLevelSize(size_t k)
	{
		if (root == nullptr) return 0;
		if (k == 1) return 1;
		return _kLevelSize(root->left, k - 1) + _kLevelSize(root->right, k - 1);
	}

	size_t _height(Node* root)
	{
		if (root == nullptr) return 0;
		size_t leftHeight = _height(root->left);
		size_t rightHeight = _height(root->right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	size_t _leafSize(Node* root)
	{
		if (root == nullptr) return 0;
		if (root->left == nullptr && root->right == nullptr) return 1;
		return _leafSize(root->left) + _leafSize(root->right);
	}

	size_t _size(Node* root)
	{
		if (root == nullptr) return 0;
		return _size(root->left) + _size(root->right) + 1;
	}

	void _preOrder(Node* root)
	{
		if(root == nullptr) return;
		cout<<root->data<<" ";
		_preOrder(root->left);
		_preOrder(root->right);
	}
	void _inOrder(Node* root)
	{
		if(root == nullptr) return;
		_inOrder(root->left);
		cout<<root->data<<" ";
		_inOrder(root->right);
	}
	void _postOrder(Node* root)
	{
		if(root == nullptr) return;
		_postOrder(root->left);
		_postOrder(root->right);
		cout<<root->data<<" ";
	}



	Node* _crtTreeInPost(const vector<T>& in, const vector<T>& post, int& posti, int inbegin, int inend)
	{
		if (inbegin > inend)return nullptr;
		Node* root = new Node(post[posti]);
		int rooti = inbegin;
		while (rooti < inend)
		{
			if (in[rooti] == post[posti])
			{
				break;
			}
			else
			{
				++rooti;
			}
		}
		--posti;
		root->right = _crtTreeInPost(in, post, posti, rooti + 1, inend);
		root->left = _crtTreeInPost(in, post, posti, inbegin, rooti - 1);
		return root;
	}

	Node* _crtTreePreMid(const vector<T>& pre, const vector<T>& in, int& prei, int inbegin, int inend)
	{
		if(inbegin > inend)
		{
			return nullptr;
		}

		Node* root = new Node(pre[prei]);
		
		int rooti = inbegin;
		while (rooti <= inend)
		{
			if (in[rooti] == pre[prei])
			{
				break;
			}
			else
			{
				++rooti;
			}
		}
		++prei;
		root->left = _crtTreePreMid(pre, in, prei, inbegin, rooti - 1);
		root->right = _crtTreePreMid(pre, in, prei, rooti + 1, inend);
		return root;
	}


	void _crtTreeStr(Node* &root, const string& str, int& pos)
	{
		if (str[pos] == SEP)
		{
			root = nullptr;
			++pos;
		}
		else
		{
			root = new Node(str[pos]);
			++pos;
			_crtTreeStr(root->left, str, pos);
			_crtTreeStr(root->right, str, pos);
		}
	}

	void _display(Node* root, int level,char c)
	{
		if (root == nullptr)
		{
			return;
		}
		int i = 0, k = 0;
		for (i = 0; i < level; ++i)
		{
			cout << " ";
		}
		cout<<root->data << "(" << c << ")+";
		for (k = i + 4; k < 80; ++k)
		{
			cout << "-";
		}
		cout << endl;
		_display(root->left, level + 4, 'L');
		_display(root->right, level + 4, 'R');
	}
private:
	Node* _root;
};


void TestCreateTreeStr()
{
	BinaryTree<char> t;
	t.crtTreeStr("ABD##E#H##CF##G##");
	t.display();
}

void TestCreateTreeEdge()
{
	BinaryTree<char> t;
	t.crtTreeEdge();
	t.display();
}

void TestCreateTreePreIn()
{
	BinaryTree<char> t;
	vector<char> pre = { 'A', 'B', 'D', 'E',  'C', 'F' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreePreIn(pre, in);
	t.display();
}

void TestCreateTreeInPost()
{
	BinaryTree<char> t;
	vector<char> post = { 'D', 'E', 'B', 'F', 'C', 'A' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreeInPost(in, post);
	t.display();
}

void TestOrder()
{
	BinaryTree<char> t;
	vector<char> pre = { 'A', 'B', 'D', 'E',  'C', 'F' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreePreIn(pre, in);
	t.preOrder();
	t.inOrder();
	t.postOrder();
}

void TestOrderNorTask()
{
	BinaryTree<char> t;
	vector<char> pre = { 'A', 'B', 'D', 'E',  'C', 'F' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreePreIn(pre, in);
	t.preOrderNorTask();
	t.inOrderNorTask();
	t.postOrderNorTask();
}

void TestOrderNorMark()
{
	BinaryTree<char> t;
	vector<char> pre = { 'A', 'B', 'D', 'E',  'C', 'F' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreePreIn(pre, in);
	t.preOrderNorMark();
	t.inOrderNorMark();
	t.postOrderNorMark();
}

void TestLevelOrder()
{
	BinaryTree<char> t;
	vector<char> pre = { 'A', 'B', 'D', 'E',  'C', 'F' };
	vector<char> in = { 'D', 'B',  'E', 'A', 'C', 'F' };
	t.crtTreePreIn(pre, in);
	t.display();
	cout << endl;
	t.levelOrder();
}